1. Field of the Invention
The present invention relates generally to an apparatus and method for coding/decoding, and in particular, to an apparatus and method for coding/decoding Repeat Accumulate (RA) codes.
2. Description of the Related Art
In communication operations, it is very important to efficiently and reliably transmit data over a channel. In the next generation multimedia mobile communication systems, i.e., systems into which active research is currently being made, it is necessary to increase system efficiency using a channel coding scheme that is appropriate for the system because there is a large demand for a high-speed communication system capable of processing and transmitting a variety of information such as image and radio data, beyond the capabilities of early voice-oriented services.
During data transmission, inevitable errors caused by noise, interference, and fading occur according to channel conditions, often resulting in a loss of information. Accordingly, in order to reduce the information loss, various error-control schemes have been used according to characteristics of channels to increase system reliability. The most typical error-control scheme uses error-correcting codes.
FIG. 1 is a block diagram illustrating a transceiver of a conventional communication system. Referring to FIG. 1, in a transmitter side, a transmission message ‘u’ is coded by an encoder 101 using a predetermined coding scheme, before being transmitted over a channel. The symbol ‘c’ coded by the encoder 101 is modulated by a modulator 103 using a predetermined modulation scheme, and the modulated signal ‘s’ is transmitted to a receiver side over a channel 105.
A signal ‘r’ is received at the receiver side. The received signal ‘r’ is a distorted signal that is a mixture of the signal ‘s’ transmitted by the transmitter side and various noises caused by a change in channel conditions of channel 105. The received signal ‘r’ is demodulated by a demodulator 107 using a demodulation scheme corresponding to the modulation scheme used in the modulator 103 of the transmitter side, and the demodulated signal ‘x’ is decoded by a decoder 109 using a decoding scheme corresponding to the coding scheme used in the encoder 101 of the transmitter side. Thereafter, the decoder 109 outputs the decoded signal û.
In order to enable the receiver side to decode the signal ‘u’ transmitted by the transmitter side without error, it is necessary to provide channel encoder and decoder having better performance. In particular, when the channel 105 is a wireless channel, errors caused by the channel 105 are more considerable. The decoder 109 of the transmitter side detects an estimated value of the transmission message using the data received over the channel 105.
Additionally, with the rapid progress of mobile communication systems, scheme for transmitting a large volume of data at and up to a capacity level presently available in wired networks must be developed for a wireless network. As a high-speed, high-capacity communication system capable of processing and transmitting various information such as image data and radio data as well as simple voice service data is required, it is necessary to increase the system transmission efficiency using an appropriate channel coding scheme in order to improve the system performance. However, as indicated above, a mobile communication system inevitably experiences errors occurring due to noise, interference, and fading according to channel conditions during data transmission. The occurrence of errors causes a loss of information data.
In order to reduce the information data loss due to the occurrence of errors, it is possible to improve reliability of the mobile communication system using various error-control schemes. As described above, the most commonly used error-control scheme uses an error-correcting code. A description will now be made of a turbo code and a low-density parity check (LDPC) code, which are typical error correcting codes.
A. Turbo Code
It is well known that the turbo code is superior in performance gain to a convolutional code conventionally used for error correction, during high-speed data transmission. The turbo code is advantageous in that it can efficiently correct an error caused by noises generated in a transmission channel, thereby increasing the reliability of the data transmission.
B. LDPC Code
The LDPC code can be decoded using an iterative decoding algorithm based on a sum-product algorithm on a factor graph. Because a decoder for the LDPC code uses the sum-product algorithm-based iterative decoding algorithm, it is lower in complexity to a decoder for the turbo code. In addition, the decoder for the LDPC code is easy to implement with a parallel processing decoder, as compared with the decoder for the turbo code.
Shannon's channel coding theorem shows that reliable communication is possible only at a data rate not exceeding a channel capacity. However, Shannon's channel coding theorem has proposed no detailed channel coding/decoding method for supporting a data rate up to the maximum channel capacity limit. Generally, although a random code having a very large block size shows performance approximating a channel capacity limit of Shannon's channel coding theorem, when a MAP (Maximum A Posteriori) or ML (Maximum Likelihood) decoding method is used, it is actually impossible to implement the decoding method because of its heavy calculation load.
The turbo code was proposed by Berrou, Glavieux, and Thitimajshima in 1993, and has superior performance approximating a channel capacity limit of Shannon's channel coding theorem. The proposal of the turbo code triggered active research on iterative decoding and graphical expression of codes. Similarly, LDPC codes proposed by Gallager in 1962 have been newly spotlighted in the research. Cycles exist on a factor graph of the turbo code and the LDPC code, and it is well known that iterative decoding on the factor graph of the LDPC code where cycles exist is suboptimal.
Also, it has been experimentally proven that the LDPC code has excellent performance through iterative decoding. The LDPC code known to have the highest performance ever shows performance having a difference of only about 0.04 [dB] at a channel capacity limit of Shannon's channel coding theorem at a bit error rate (BER) 10−5, using a block size 107. In addition, although an LDPC code defined in Galois Field (GF) with q>2, i.e., GF(q), increases in complexity in its decoding process, it is far superior in performance to a binary code. However, no satisfactory theoretical description of successful decoding by an iterative decoding algorithm for the LDPC code defined in GF(q) has yet been provided.
More specifically, the LDPC code, proposed by Gallager, is defined by a parity check matrix in which major elements have a value of 0 and minor elements except the elements having the value of 0 have a non-zero value, i.e., a value of 1. For example, an (N, j, k) LDPC code is a linear block code having a block length N, and is defined by a sparse parity check matrix in which each column has j elements having a value of 1, each row has k elements having a value of 1, and all of the elements except for the elements having the value of 1 have a value of 0.
An LDPC code in which a weight of each column in the parity check matrix is fixed to ‘j’ and a weight of each row in the parity check matrix is fixed to ‘k’ as stated above, is called a “regular LDPC code.” Herein, the “weight” refers to the number of elements having a non-zero value among the elements constituting the generating matrix and parity check matrix.
Unlike the regular LDPC code, an LDPC code in which the weight of each column in the parity check matrix and the weight of each row in the parity check matrix are not fixed is called an “irregular LDPC code.” It is generally known that the irregular LDPC code is superior in performance to the regular LDPC code. However, in the irregular LDPC code, because the weight of each column and the weight of each row in the parity check matrix are not fixed, i.e., are irregular, the weight of each column in the parity check matrix and the weight of each row in the parity check matrix must be properly adjusted in order to guarantee the superior performance.
FIG. 2 illustrates a parity check matrix of an (8, 2, 4) LDPC code, e.g., an (N, j, k) LDPC code. More specifically, FIG. 2 is a diagram illustrating a parity check matrix of a general (8, 2, 4) LDPC code.
Referring to FIG. 2, a parity check matrix H of the (8, 2, 4) LDPC code is comprised of 8 columns and 4 rows, wherein a weight of each column is fixed to 2 and a weight of each row is fixed to 4. Because the weight of each column and the weight of each row in the parity check matrix are regular as stated above, the (8, 2, 4) LDPC code illustrated in FIG. 2 becomes a regular LDPC code.
FIG. 3 is a diagram illustrating a factor graph of the (8, 2, 4) LDPC code illustrated in FIG. 2. Referring to FIG. 3, a factor graph of the (8, 2, 4) LDPC code is comprised of 8 variable nodes of x1 300, x2 302, x3 304, x4 306, x5 308, x6 310, x7 312, and x8 314, and 4 check nodes 316, 318, 320, and 322. When an element having a value of 1, i.e., a non-zero value, exists at a point where an ith row and a jth column of the parity check matrix of the (8, 2, 4) LDPC code cross each other, a branch is created between a variable node xi and a jth check node.
Because the parity check matrix of the LDPC code has a very small weight as described above, it is possible to perform decoding through iterative decoding even in a block code having a relatively long length, that exhibits performance approximating a capacity limit of a Shannon channel, such as a turbo code, while continuously increasing a block length of the block code. MacKay and Neal have proven that an iterative decoding process of an LDPC code using a flooding transfer scheme is approximate to an iterative decoding process of a turbo code in performance.
However, in order to generate a high-performance LDPC code, the following conditions should be satisfied.
(1) Cycles on a Factor Graph of an LDPC Code should be Considered.
The term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A cycle being long in length indicates that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. In contrast, a cycle being short in length indicates that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is small.
As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases. That is, when long cycles are generated in the factor graph of the LDPC code, it is possible to prevent performance degradation such as an error floor occurring when too many cycles with a short length exist on the factor graph of the LDPC code.
(2) Efficient Coding of an LDPC Code should be Considered.
It is difficult for the LDPC code to undergo real-time coding compared with a convolutional code or a turbo code because of its high coding complexity. In order to reduce the coding complexity of the LDPC code, a Repeat Accumulate (RA) code has been proposed. However, the RA code also has a limitation in reducing the coding complexity of the LDPC code. Therefore, efficient coding of the LDPC code should be considered.
(3) Degree Distribution on a Factor Graph of an LDPC Code should be Considered.
Generally, an irregular LDPC code is superior in performance to a regular LDPC code, because a factor graph of the irregular LDPC code has various degrees. The term “degree” refers to the number of edges connected to the variable nodes and the check nodes in the factor graph of the LDPC code. Further, the phrase “degree distribution” on a factor graph of an LDPC code refers to a ratio of the number of nodes having a particular degree to the total number of nodes. It has been proved by Richardson that an LDPC code having a particular degree distribution is superior in performance.
As described above, it is well known that the LDPC code, together with the turbo code, are superior in a performance gain for high-speed data transmission, and the LDPC code is advantageous in that it can efficiently correct errors caused by noises generated in a transmission channel, thereby increasing the reliability of the data transmission.
However, the LDPC code is not free in terms of coding rate. That is, because the LDPC code has a relatively high coding rate, it has limitation in terms of coding rate. In the current LDPC codes, most have a coding rate of ½ and only some have a coding rate of ⅓. The limitation in coding rate exerts a fatal influence on high-speed, high-capacity data transmission. Of course, although a degree distribution representing the best performance can be calculated using a density evolution scheme in order to implement a relatively low coding rate for the LDPC code, it is difficult to implement an LDPC code having a degree distribution representing the best performance due to various restrictions, such as a cycle structure on a factor graph and hardware implementation. In addition, the LDPC code makes it difficult to enable real-time coding and causes a delay in a decoding process.